package main

import "fmt"

func main() {
	jobs := []int{3, 2, 3}
	k := 3
	fmt.Println(minimumTimeRequired(jobs, k))
}

var (
	_k, n  int
	_jobs  []int
	result = 1 << 31
)

func minimumTimeRequired(jobs []int, k int) int {
	_k = k
	_jobs = jobs
	n = len(jobs)
	result = 1 << 31
	backTrace(0, 0, make([]int, k), 0)
	return result
}

/**
 * u     : 当前处理到那个 job
 * used  : 当前分配给了多少个工人了
 * sum   : 工人的分配情况          例如：sum[0] = x 代表 0 号工人工作量为 x
 * max   : 当前的「最大工作时间」
 */
func backTrace(u, used int, sum []int, max int) {
	if max >= result {
		return
	}
	//当工作分配完了，更新result的最大值
	if u == n {
		result = max
		return
	}
	if used < _k {
		sum[used] = _jobs[u]
		backTrace(u+1, used+1, sum, maxNum(sum[used], max))
		sum[used] = 0
	}
	//k个工人
	for i := 0; i < used; i++ {
		sum[i] += _jobs[u]
		backTrace(u+1, used, sum, maxNum(sum[i], max))
		sum[i] -= _jobs[u]
	}
}

func maxNum(a, b int) int {
	if a > b {
		return a
	}
	return b
}
